The present invention relates to communication networks. More particularly, the present invention relates to a system and method for recovering and managing location information in mobile communication networks.
Communications networks that include mobile stations such as cellular telephones typically include some mechanism for tracking the location of the mobile hosts (sometimes referred to herein as xe2x80x9cmobilesxe2x80x9d) in order to establish connections with the mobile hosts. Generally, each mobile reports its location to the mobile communication network, which stores the location information in one or more location information databases (LIDs). The location information is later retrieved from the LID to establish connections with the mobiles. Conventional approaches to updating the location information for mobiles include having each mobile send a location update message after either a predetermined time period has elapsed andlor the mobile has moved a predetermined distance since the mobile last sent a location update message.
A conventional mobile communication network 10 of the type generally referred to as a personal communications services network (PCS) is shown in FIG. 1. The mobile communication network 10 has a conventional cellular architecture for providing more efficient use of bandwidth. The mobile communication network comprises a plurality of cells 12 in which mobiles can be located. Each cell 12 has a base station 14 (shown in FIG. 2) for establishing wireless links with mobiles 16 (shown in FIG. 2) in the cell 12.
A set of base stations 14 is controlled by a base station controller (BSC) 18 (shown in FIG. 1). The primary function of a BSC 18 is to manage the radio resources of the base stations 14 controlled by the BSC 18, for example, by performing call hand-off and allocating radio channels. Each BSC 18 is connected to a mobile switching center (MSC) 20 through a wired network 22. Each MSC 20 is typically connected to more than one BSC 18 and has a location area 24 that includes all of the cells 12 under the control of BSCs 18 that are connected to the MSC 20. The MSC 20 typically provides switching functions and coordinates location registration and call delivery for mobiles 16 located within the location area 24 of the MSC 20. Each MSC 20 has access to the location information databases in the mobile communication network 10, which are used to store location and service information for each registered mobile 16 of the mobile communication network 10.
Mobile communication networks 10 that comply with the IS-41 standard (which is described in EIA/TIA, xe2x80x9cCellular Radio Telecommunications Intersystems Operation,xe2x80x9d PN-2991, November 1995, and is incorporated by reference) use a two-level hierarchy of location information databases for location management. Location information databases that adhere to the IS-41 standard have a home location register (HLR) 26 and one or more visitor location registers (VLRs) 28. The HLR 26 is a global database in which information (including location information) about all mobiles 16 registered in the mobile communication network 10 is stored. Each VLR 28 is typically associated with a single MSC 20 and stores information (including location information) about mobiles visiting the location area 24 of the MSC 20 associated with that VLR 28.
In mobile communication networks 10 that comply with the IS-41 standard, the HLR 26 and the VLRs 28 are updated with location information from mobiles 16 as shown in FIG. 3. Initially, a mobile 16 is located in a first location area 24a that is associated with a first MSC 20a and a first VLR 28a (which has an entry for the mobile 16). Then the mobile 16 moves into a second location area 24b associated with a second MSC 20b and a second VLR 28b. The mobile 16 sends a location update message 30 to the second MSC 20b, and the MSC 20b sends a location update message 32 containing location information about the mobile 16 to the HLR 26. After receiving the location update message 32, the HLR 26 updates the entry that the HLR 26 has for the mobile 16 with the location information contained in the location update message 32, sends a confirmation message 34 back to the second MSC 20b, and sends a deletion message 36 to the first MSC 20a. After receiving the confirmation message 34 from the HLR 26, the second MSC 20b creates an entry in the second VLR 28b for storing the location information for the mobile. After receiving the deletion message 36 from the HLR 28, the first MSC 20a deletes the entry for the mobile 16 in the first VLR 28a. 
The call delivery protocol (CDP) of the IS-41 specifies how the location information stored in the location information databases can be used to complete telephone calls between first and second mobiles 16a and 16b. As shown in FIG. 4. when the first mobile 16a places a telephone call to the second mobile 16b, the first mobile 16a sends a call delivery request (CDR) 40 to the first MSC 20a. The first MSC 20a queries the first VLR 28a associated with the first MSC 20a to determine if the first VLR 28a has an entry for the second mobile 16b. If the first VLR 28a has an entry for the second mobile 16b, i.e., if the second mobile 16b is located within the first location area 24a associated with the first MSC 20a and the first VLR 28a, the first MSC 20a establishes a connection between the first and second mobiles 16a and 16b, assuming the second mobile 16b is in a mode to receive calls. If the first VLR 28a does not have an entry for the second mobile 16b, i.e., if the second mobile 16b is not located within the first location area 24a, the first MSC 20a sends a query 42 to the HLR 26 for the second mobile""s 16b location information. The HLR 26 determines the current location area 24b for the second mobile 16b from the entry stored in the HLR 26 for the second mobile 16b and sends a route request 44 to the second MSC 20b that is associated with the location area 24b in which the second mobile 16b is located. The second MSC 20b determines a temporary location directory number for the second mobile 16b (assuming the second mobile is in a mode to receive calls) and transfers the information 46 to the HLR 26. The HLR 26 sends the information 48 to the first MSC 20a, and the MSC 20a establishes a connection 50 between the first and second mobiles 16a and 16b. If a fixed host (that is, a host in the wired network) calls the first mobile 16a, the call is routed to the first MSC 20a using the location information in the HLR 26. If the first mobile 16a calls a fixed host, the first MSC 20a establishes the connection with the fixed host without referring to the HLR 26; therefore, the delivery of a call from the first mobile 16a to a fixed host does not depend on the state of the HLR 26.
Therefore, calls between two mobiles in different location areas and calls from a fixed host to a mobile typically cannot be completed without using the location information stored in the HLR 26. As a result, if the location information stored in the HLR 26 is inaccessible, calls between two mobiles in different location areas and calls from a fixed host to a mobile typically cannot be completed and will be dropped. The HLR 26 will be inaccessible, for example, because the HLR 26 is inoperable, referred to herein as a xe2x80x9cdatabase failure,xe2x80x9d or because the portion of the mobile communication network 10 providing access to the HLR 26 is inoperable, referred to herein as a xe2x80x9clink failure.xe2x80x9d To avoid extended periods where the HLR 26 is inoperable, conventional mobile communication networks 10 use HLRs 26 that can be restored relatively quickly after a database failure so that the time in which the HLR 26 is inoperable (referred to herein as the xe2x80x9cfailure periodxe2x80x9d) is minimized. Such conventional HLRs 26 typically have fail-stop, stable disk storage, e.g., redundant arrays of disks. Also, it is known to periodically back up the volatile memory of such HLRs 26 to the disk storage and to log transactions on the disk storage between backups.
Even after the failure has been removed from the mobile communication network 10, calls that rely on information in the HLR 26 in order to be completed can still not be completed because the mobiles 16 registered with the HLR 26 may have moved to different location areas during the failure period. Because the HLR 26 is inaccessible during a failure period, the location update messages that are sent to the HLR 26 when the mobile 16 enters a new location area 24 cannot be properly processed by the HLR 26. Therefore, even though the HLR 26 is restored to the state the HLR 26 was in just prior to the failure, the HLR 26 may not reflect the current location of any mobiles 16 that have moved during the failure period. This period in which the state of the HLR 26 may not reflect the current location of a mobile 16 registered with the HLR 26 is referred to herein as the xe2x80x9crecovery period.xe2x80x9d For each mobile 16 registered with the HLR 26, the recovery period starts when the HLR 26 becomes accessible after a database failure or a link failure and ends when the contents of the HLR 26 have been updated and/or verified to contain the current location information for that mobile 16.
One known approach to updating and/or verifying (collectively referred to herein as xe2x80x9crecoveringxe2x80x9d) the entries stored in the HLR 26 for each mobile 16 registered therewith involves sending an unreliable roamer data directive (URDD) to the VLRs 28 associated with the HLR 26. In response to the URDD, each VLR 28 removes from its database those entries for the mobiles 16 registered with the HLR 26. Subsequently, the HLR 26 is reconstructed in an incremental fashion as each mobile 16 registered with the HLR 26 confirms the mobile""s location by making a call or by sending a location update message when the mobile 16 enters a new location area 24. The IS-41 standard, referred to above, also specifies that each mobile 16 should periodically transmit location update messages, regardless of whether the mobile 16 has entered a new location area and regardless of the state of the HLR 26, in order to reduce the recovery period. During the failure period and recovery period, all calls made to the mobile 16 will not be completed.
The IS-41 standard recovery process has the following primary drawbacks. A periodic location update message is sent from each mobile 16 regardless of the state of the HLR 26, which wastes wireless bandwidth when periodic location update messages are transmitted when the HLR 26 is not in a recovery period. This drawback is magnified if the population of mobiles 16 is large. The periodic transmission of location update messages as required by the IS-41 standard also results in power drain for the mobiles 16. However, for such an approach to be effective, the frequency of the periodic location update messages must be comparable to the frequency of incoming calls. In addition, any further reduction in the recovery period can only be achieved by increasing the frequency of the periodic location update messages, which results in greater use of the wireless bandwidth, greater power drain for the mobiles 16, and a greater load on the HLR 26.
Another known recovery approach addresses the limitations of using a fixed location update message transmission interval by using a variable location update message transmission interval that is a function of various network parameters (such as call arrival rates, mobility rates, and mean time between HLR failures) in order to optimize the periodic location update message transmission interval. In order to adapt to changes in the network parameters efficiently, the network has to periodically feed data to the mobiles 16 in the network. This increases the processing load of the mobiles 16, which results in further power drain and requires that the mobiles 16 possess computational and storage abilities to adapt the location update message transmission interval based on the received data.
Yet another known recovery process has the HLR 26, after a failure has been removed, get the current location information from the VLRs 28. To reduce the amount of information to be exchanged, the HLR 26 requests only the information about mobiles 16 that have moved after the last checkpoint the HLR 26 took before the failure. If the HLR 26 is not checkpointed frequently, this approach may require high communication overhead resulting from the large amounts of information being transferred from the plurality of VLRs 28 to the HLR 26. Also, in such an approach, the clocks of the HLRs 26 and VLRs 28 must be synchronized.
Therefore, there is a continuing need for an improved location information recovery and management system and method.
Implementations may include one or more of the following features. In one aspect, a method for managing information concerning the location of a mobile device in a mobile communication network may include maintaining a location database that stores location information indicative of the location of the mobile device. The method also may include receiving location update messages from the mobile device via a location update processor associated with a particular location area within the network when the location of the mobile device changes. In addition, the method may include transmitting the location update messages to the location database. In the event one of the location update messages is not received by the location database, location update retry messages are transmitted at the end of successive retry intervals until one of the location update retry messages is received.
In another aspect, a mobile communication network may include a mobile device, a location database server having a location database storing location information indicative of the location of the mobile device, and a location update processor. The location update processor receives location update messages from the mobile device when the location of the mobile device changes and transmits the location update messages to the location database. In the event one of the location update messages is not received by the location database, the location update processor transmits location update retry messages at the end of successive retry intervals until one of the location update retry messages is received.
In another aspect, a location database server may include a location database and a recovery processor. The location database server receives location update messages and location update retry messages. The location update messages are transmitted by a location update processor when a mobile device enters a location area associated with the location update processor. The location update retry messages are transmitted at the end of successive retry intervals by the location update processor in the event one of the location update messages is not received by the location database server. The location update messages have time stamps, and the location update retry messages include the time stamps from the unreceived location update message. The location database is for storing location information indicative of the location of the mobile device. The recovery processor is for recovering location information for the mobile device after a failure in the mobile communication network is fixed. In the event that a location update message is received before the retry interval has passed since the failure was fixed, the recovery processor stores in the location database the location information for the mobile device from the location update message. In the event that the retry interval has passed since the failure was fixed without receiving a location update message while receiving at least one location update retry message, the recovery processor stores in the location database the location information for the mobile device from the location update retry message having the most recent time stamp.
In another aspect, a location update processor may include a receiver and a message processor. The location update processor is for use in a mobile communication network having a mobile device and a location database server having a location database storing location information indicative of the location of the mobile device. The receiver receives location update messages from the mobile device when the location of the mobile device changes, and the message processor transmits location update messages to the location database server. In the event one of the location update messages is not received by the location database, the message processor transmits location update retry messages at the end of successive retry intervals until one of the location update retry messages is received.
In another aspect, a method may operate in a distributed database system having n database servers, D1, . . . , Dn, arranged in a logical ring. The method is a method of updating k of the database servers, Dxcex31, . . . , Dxcex3k, referred to by a placement vector xcex93=(xcex31, . . . , xcex3k), where xcex3ixcex5{1, . . . , n} is the index of the ith database server updated by the method. The method may include selecting xcex31 from the set (1, . . . , n). Also, the method may include for i=1, . . . , kxe2x88x921, selecting xcex3i+1 according to xcex3i⊕└n/k┘+ai, where ⊕ is modulo addition defined over the set (1,2, . . . , n), displacement vector xc3xa2=(a1, . . . , ak) is a binary vector having a Hamming weight of xcex2, and xcex2=nxe2x88x92└n/k┘*k. The method may further include updating the k database servers, Dxcex31, . . . , Dxcex3k, referred to by the placement vector xcex93=(xcex31, . . . , xcex3k) with updated information.
In another aspect, a method may operate in a distributed database system having n database servers, D1, . . . , Dn, arranged in a logical ring for storing information about a first group of items in k, of the database servers and for storing information about a second group of items in k2 of the database servers, wherein k1 greater than k2. The method is a method of querying the database servers for information about a given item. The method may include selecting a first database server D1 and determining in parallel if any of ┌n/k┐ successive database servers, Di, Di+1, . . . , Di⊕┌n/k1┐, contain information about the given item. If at least one of the ┌n/k1┐ successive database servers, Di, . . . , Di⊕┌n/k1┐, does not contain information about the given item, the method may determine in parallel if any of the next (┌n/k1┐-┌n/k2┐) successive database servers, Di⊕┌n/k1┐⊕1, . . . , Di⊕┌n/k2┐, contain information about the given device. If at least one of the next (┌n/k2┐-┌n/k1┐) successive database servers, Di⊕┌n/k1┐⊕1, . . . , Di⊕┌n/k2┐, does not contain information about the given item, then until information for the given item is found or until all the database servers D1, . . . , Dn, have been checked, the method may determine in parallel if successive groups of ┌n/k2┐ database servers, Di⊕(j*┌n/k2┐)⊕1, . . . , Di⊕(j+1)*┌n/k2┐, contain information for the given item, where j represents the jth group of ┌n/k2┐ database servers that are checked.
In another aspect, a method of updating a database over a network with information from a device may include receiving update messages from the device via a processor connected to the network and transmitting the update messages to the database. In the event one of the update messages is not received by the database, the method may transmit update retry messages at the end of successive retry intervals until one of the update retry messages is received.
One or more of the following advantages may be realized. The fast recovery protocol does not require the use of wireless bandwidth during the recovery process, has a bounded recovery period, and is relatively simple to implement. The fast recovery protocol can be used to recover from both database and link failures, and can be adapted to recover from failures in both global and local location information databases. Moreover, the fast recovery protocol can be used with both centralized and distributed database architectures. When the fast recovery protocol is used with a distributed database architecture, the protocol can be implemented with load-balanced, fault-tolerant update processes and robust, parallel query processes.